package 分类.前缀和;

import org.w3c.dom.Node;

public class 二维区域和检索矩阵不可变 {
    public static void main(String[] args) {
        int[][] nums={{3,0,1,4,2},{5,6,3,2,1},{1,2,0,1,5},{4,1,0,1,7},{1,0,3,0,5}};

        int m=nums.length;
        int n=nums[0].length;

        int[][] preSum=new int[m][n];
        for (int i=0;i<m;i++){
            preSum[i][0]=nums[i][0];
        }
        for (int j=0;j<n;j++){
            preSum[0][j]=nums[0][j];
        }
        for(int i=1;i<m;i++){
            for (int j=1;j<n;j++){
                preSum[i][j]=preSum[i-1][j]+preSum[i][j-1]+nums[i][j]-preSum[i-1][j-1];
            }
        }

       //2143
       System.out.println(preSum[4][3]-preSum[1][3]-preSum[4][0]+preSum[1][0]);
    }



}




